<Consistent Hash Method>
In recent years, there have been increasing attempts to implement a distributed storage system, more specifically, a storage system having scalable performance by distributing and arranging data using a hash function. As a method of distributing and arranging data using the hash function, there is used a consistent hash method (described in each of Non-patent Documents 1 and 2), for example.
In the consistent hash method, data is distributed and arranged in a plurality of storage apparatuses (for which computer apparatuses such as IA servers (servers, each of which has one or more Intel's microprocessors mounted), each constituted from a CPU and a memory, are applicable). In a system to which the consistent hash method is applied, there is provided a distributed hash table or the like.
The reason why the consistent hash method as described above is used as the distributing and arranging method is as follows.
Even if a storage apparatus is added or deleted, there is no need to rearrange the distribution of whole data again in order to maintain a distributed and recorded state of the data.
Further, even if a fault occurs in one of the plurality of storage apparatuses, restoration can be flexibly performed.
Non-patent Document 3 discloses an example of the distributed storage system in which data is arranged in a distributed manner, using the consistent hash method. FIG. 1 is a citation of FIG. 2 of Non-patent Document 3 without alteration.
The distributed storage system disclosed in Non-patent Document 3 generally operates as follows. According to Non-patent Document 3, a node (Node) that stores data whose key (Key) is K (the hash value of data is K when Key is to be found by the hash value) is determined as a node B, using the consistent hash method. This is because the node B is a first node when the hash ring is traversed in a clockwise direction from the position of K. A storage apparatus constituting the distributed storage system may fail. Thus, preferably, data is stored in different storage apparatus, as well. In the distributed storage system in Non-patent Document 3, the data having the key value of K is stored in three storage apparatuses and hence the data having the key value of K is stored in nodes C and D as well, by further traversing the hash ring from the node B in the clockwise direction. Keys located in the range between the nodes A and B are stored in the nodes B, C, and D.
The configuration method of the distributed storage system using the hash function as described above is not only used for storing master data, as described in Non-patent Document 3, but also is used as a mechanism for storing a cache (temporary data that may be) of the master data. In this case, the distributed storage system operates in such a manner that the master data is recorded in a different storage system (such as a database system), and a client who will read the data accesses the distributed storage system for the cache, without accessing the storage system of the master data.    [Non-patent Document 1]    David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy, “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web”, In ACM Symposium on Theory of Computing, 1997    [Non-patent Document 2]    Tom White's Blog: Consistent Hashing, http://weblogs. java. net/blog/tomwhite/archive/2007/11/consistent_hash.html, accessed on Feb. 27,2009    [Non-patent Document 3]    Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Silvasubramanian, Peter Vosshall and Werner Vogels, “Dynamo: Amazon's Highly Available Key-Value Store”, in the Proceedings of the 21st ACM Symposium on Operating Systems Principles, Stevenson, WA, Oct. 2007.